package com.cat.chapter052;

import java.io.*;

/**
 * @author cat
 * @description https://www.nowcoder.com/practice/2a2c00e7a88a498693568cef63a4b7bb
 * @create 2025/7/23 10:25
 * @since JDK17
 */

public class Solution01 {
    static int N = ((int) (1e6 + 10)), n;
    static int[] stack = new int[N], arr = new int[N];
    static int[][] ans = new int[N][2];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pr = new PrintWriter(new OutputStreamWriter(System.out));
    static StreamTokenizer tokenizer = new StreamTokenizer(br);
    public static void main(String[] args) throws IOException {
        tokenizer.nextToken();
        n = ((int) tokenizer.nval);
        for (int i = 0; i < n; i++) {   // 输入n个数字
            tokenizer.nextToken();
            arr[i] = ((int) tokenizer.nval);
        }
        int r = 0, cur;
        for (int i = 0; i < n; i++) {
            while (r > 0 && arr[stack[r - 1]] >= arr[i]) {  // 弹出
                cur = stack[--r];   // 上一个位置
                ans[cur][0] = r <= 0 ? -1 : stack[r - 1];
                ans[cur][1] = i;
            }
            stack[r++] = i; // 放入一个数字
        }

        while (r > 0) {
            cur = stack[--r];
            ans[cur][0] = r <= 0 ? -1 : stack[r - 1]; // 下面的位置
            ans[cur][1] = -1;
        }

        for (int i = n - 2; i >= 0; i--) {
            if (ans[i][1] != -1 && arr[ans[i][1]] == arr[i]) {
                ans[i][1] = ans[ans[i][1]][1];
            }
        }
        for (int i = 0; i < n; i++) {
            pr.println(ans[i][0] + " " + ans[i][1]);
        }
        pr.flush();
        pr.close();
        br.close();
    }
}
